ABC 399D

题目内容

有 $N$ 对夫妇，编号为 $1, 2, \dots, N$ 。这 $2 N$ 个人正在排队。试问有多少个夫妇对 $⟨ i, j ⟩$ ，满足夫妇 $i$ 与夫妇 $j$ 起初均不相邻，但可以通过仅重排这四个人的位置就能让两对夫妻各自相邻？

解法

错误解法

容易注意到满足条件的 $(i, j)$ 在序列中应当形如

\dots, i, j, \dots, i, j, \dots

或

\dots, i, j, \dots, j, i, \dots

考虑直接遍历整个序列所有的相邻对 $(x, y)$ （代码中会自动处理成 $x \leq y$ 的形式）临时作下记录后继续寻找形如 $(x, y)$ 与 $(y, x)$ 的相邻对，找到后答案计数加一。为了防止重复计算，可维护一个 set 负责记录所有已经被找到的对。

解答

错解对于需要寻找的形式的判断没有问题，但问题出在寻找这种形式的实现上。错解的实现对形如

\dots, i, j, i, \dots, j, \dots

的序列特别难以处理。错解最初没有加上位置判断，因此会算多；但假若加上各种基于位置的判断则会比标答臃肿许多，不如丢掉重写。

正确的做法是，利用上题目给出的“每个数在序列中恰好出现两次”的条件，先以 $Θ (n)$ 的时间复杂度扫一遍序列，记录下每个数的两次出现位置，再 $Θ (n)$ 扫一遍所有的相邻对 $(i, j)$ ，基于先前记录下的 $i$ 的出现位置与 $j$ 的出现位置就能很轻松地判断是否符合我们要找的形式。当然还是要注意不要重复计算。

AC 代码

见提交记录

感想

到底是怎么做到明明已经想出来做法结果硬调了一个半小时没写出正确代码的？